package com.sunny.排序.快速排序;

import com.sunny.util.ArrayUtil;

public class QuickSort {
    public static int[] quickSort(int size) {
        // 开始执行时间
        long start = System.currentTimeMillis();
        // 数组初始化
        int[] array = ArrayUtil.instanceArray(size);
        // 排序
       sort(array, 0, size - 1);
        // 结束时间
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
        return array;
    }

    private static void sort(int[] array, int low, int high) {
        if(low < high) {
            int middle = getMiddle(array, low, high);
            sort(array, low, middle - 1);
            sort(array, middle + 1, high);
        }
    }

    private static int getMiddle(int[] numbers, int low, int high) {
        int key = numbers[low];
        while (low < high) {
            while (low < high && numbers[high] >= key)
                high--;
            numbers[low] = numbers[high];
            while (low < high && numbers[low] <= key)
                low++;
            numbers[high] = numbers[low];
        }
        numbers[low] = key;
        return low;
    }
}
